#include <iostream>
#include <stdlib.h>
#include <vector>
#include <algorithm>
#include "BinarySearchTree.h"

using namespace std;

template <typename Comparable>
void print(const vector<Comparable> &_arr){
    for(int i:_arr)cout<< i << " ";
    cout<< "\n";

};//打印arr


template <typename Comparable>
void random(vector<Comparable> &_arr) {
    int len = _arr.size();
    for(int i = len - 1; i >= 0; i--) {
        int randomIndex = rand()%len;  //获取一个0-len之间的随机数
        Comparable temp = _arr[randomIndex];
        _arr[randomIndex] = _arr[i];
        _arr[i] = temp;//将 _arr[randomIndex] 和 _arr[i]互换
    }
}//用于随机序列，时间复杂度为n

template <typename Comparable>
void check(vector<Comparable> &arr) {
    int u=1;
    for (int i = 0; i < arr.size()-1; i++)
         if (arr[i]<arr[i+1])u++;
    if(u== arr.size()){
        random(arr);
        check(arr);//递归防止出现仍不为乱序
    }
    
}

int main(){
    vector<int> arr;
    for(int i=0; i < 5; i++)
        arr.push_back(rand());//随机输入5个数
    
    print(arr);
    
    check(arr);

    print(arr);

    BSTSorting(arr);
    
    print(arr);
    
    return 0;
}
